class Solution {
public:
    // 回溯算法解决n个for循环问题

    string letterMap[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    string str;     // 记录每条路径的字符串

    void Combine(const string& digits, int index, vector<string>& ret)
    {
        if(index == digits.size())
        {
            ret.push_back(str);
            return;
        }

        int digit = digits[index] - '0';
        string letter = letterMap[digit];

        for(size_t i = 0; i < letter.size(); i++)
        {
            str.push_back(letter[i]);
            Combine(digits, index + 1, ret);
            str.pop_back();
        }

    }

    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0)
            return {};
        
        vector<string> ret;

        int index = 0;

        Combine(digits, index, ret);

        return ret;
    }
};